package code3;

import java.util.ArrayList;
import java.util.Random;

/**
 * 测试添加操作:数据是顺序的
 BST:可能会退换成链表--这里不测试
 AVL: 7.1507645 s
 RBTree: 6.6020718 s
 */

public class Main3 {

    public static void main(String[] args) {

        // int n = 20000000;
        int n = 20000000;


        ArrayList<Integer> testData = new ArrayList<>(n);
        for(int i = 0 ; i < n ; i ++) {
            testData.add(i);
        }

//        // Test BST
//        long startTime = System.nanoTime();
//
//        BSTMap<Integer, Integer> bst = new BSTMap<>();
//        for (Integer x: testData) {
//            bst.add(x, null);
//        }
//
//        long endTime = System.nanoTime();
//
//        double time = (endTime - startTime) / 1000000000.0;
//        System.out.println("BST: " + time + " s");


        // Test AVL
        long startTime = System.nanoTime();

        AVLTree<Integer, Integer> avl = new AVLTree<>();
        for (Integer x: testData) {
            avl.add(x, null);
        }

        long endTime = System.nanoTime();

        double time = (endTime - startTime) / 1000000000.0;
        System.out.println("AVL: " + time + " s");


        // Test RBTree
        startTime = System.nanoTime();

        RBTree<Integer, Integer> rbt = new RBTree<>();
        for (Integer x: testData) {
            rbt.add(x, null);
        }

        endTime = System.nanoTime();

        time = (endTime - startTime) / 1000000000.0;
        System.out.println("RBTree: " + time + " s");
    }
}
